import java.util.*;

public class Rezolvare {
	@SuppressWarnings("rawtypes")
	Stack btStack=new Stack();
	Operator op[]={new Op12(),new Op13(),new Op21(),new Op24(),new Op31(),new Op34(), new Op42(), new Op43()};
	@SuppressWarnings("unchecked")
	public void solving(Matrice stare)
	{
		/** Expandez un nou nod */
		Matrice s=expand(stare);
		/** Daca nodul expandat nu se mai gaseste in stiva starilor atunci */
		if(!search(s))
		{ /* Adaug noul nod in stiva */
			btStack.push(s);
			/* Verific daca noul nod adaugat in stiva este solutie */
			if(solutie(s))
			{
				System.out.println("Tabla cu regine este:");
				int m[][]=stare.getM();
				for(int i=0;i<m.length;i++)
				{
					for(int j=0;j<m.length;j++)
						System.out.print(m[i][j]+" ");
					System.out.println();
				}
				return;
			}
			else // daca noul nod nu este solutie atunci continui cautarea
				solving(s);
		}
		else // in caz ca nodul expandat este deja in stiva
			if(btStack.size()!=0){
				Matrice c=(Matrice)btStack.elementAt(btStack.size()-1);
				solving(c);
			}
	}
	public Matrice expand(Matrice stare){
		Matrice temp=new Matrice(stare.getM(), stare.getNrReg());
		if(op[0].valabil(temp) && op[0].skip==false)
		{
			temp=op[0].execute(temp);
			op[0].skip=true;
		}
		else if(op[1].valabil(temp)&& op[1].skip==false)
		{
			temp=op[1].execute(temp);
			op[1].skip=true;
		}
		else if(op[2].valabil(temp) && op[2].skip==false)
		{
			temp=op[2].execute(temp);
			op[2].skip=true;
		}
		else if(op[3].valabil(temp) && op[3].skip==false)
		{
			temp=op[3].execute(temp);
			op[3].skip=true;
		}
		else if(op[4].valabil(temp) && op[4].skip==false)
		{
			temp=op[4].execute(temp);
			op[4].skip=true;
		}
		else if(op[5].valabil(temp)&& op[5].skip==false)
		{
			temp=op[5].execute(temp);
			op[5].skip=true;
		}
		else if(op[6].valabil(temp)&& op[6].skip==false)
		{
			temp=op[6].execute(temp);
			op[6].skip=true;
		}
		else if(op[7].valabil(temp)&& op[7].skip==false)
		{
			temp=op[7].execute(temp);
			op[7].skip=true;
		}
		return temp;
	}

	public boolean solutie(Matrice s){
		boolean r=false;
		if(s.getNrReg()==4)
			r=true;
		return r;
	}

	@SuppressWarnings("unchecked")
	//initializam starea initiala
	public void init(){
		int m[][]=new int[4][4];
		for(int i=0;i<m.length;i++)
			for(int j=0;j<m.length;j++)
				m[i][j]=0;
		btStack.push(new Matrice(m,0));
	}
	
	public boolean search(Matrice s){
		boolean r=false;
		for(int i=0;i<btStack.size();i++)
			if(((Matrice)btStack.elementAt(i)).equals(s))
			{
				return true;
			}
		return r;
	}
}